/* 
 * $Id: StateCache.java 1259 2007-01-09 14:23:47Z tcoupaye $
 *
 * Behavior Protocols extensions for static and runtime checking
 * developed for the Julia implementation of Fractal.
 *
 * Copyright 2004
 *    Distributed Systems Research Group
 *    Department of Software Engineering
 *    Faculty of Mathematics and Physics
 *    Charles University, Prague
 *
 * Copyright (C) 2006
 *    Formal Methods In Software Engineering Group
 *    Institute of Computer Science
 *    Academy of Sciences of the Czech Republic
 *
 * Copyright (C) 2006 France Telecom
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
 *
 * Contact: ft@nenya.ms.mff.cuni.cz
 * Authors: Jan Kofron <kofron@nenya.ms.mff.cuni.cz>
 */

package org.objectweb.fractal.bpc.checker.DFSR;

import java.util.HashMap;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.NoSuchElementException;

import org.objectweb.fractal.bpc.checker.parser.Debug;
import org.objectweb.fractal.bpc.checker.state.Signature;

/**
 * This class implements the cache for states while passing the state space of
 * the protocol. The performance of this class is crucial for the checking
 * speed.
 * 
 * In order to be as fast as possible the HashSet is used. The performance of
 * this data structure can be fine-tuned via parameters 'load factor' (0.75 is
 * the default value) and 'initial capacity'.
 */
public class StateCache {

    /**
     * Creates a new instance of StateCache.
     * 
     * @param maximalcapacity
     *            the maximal capacity of the cache. In the case the cache
     *            becomes full, some states are deleted from the cache.
     */
    public StateCache(int maximalcapacity) {

        int initialcapacity = 1000;
        cache = new HashMap(initialcapacity, load);
        if (maximalcapacity != 0)
            this.maximalCapacity = maximalcapacity;
        else
            this.maximalCapacity = Integer.MAX_VALUE;

        Debug.println(2, "Cache created with capacity of " + this.maximalCapacity + " items.");

    }

    /**
     * Inserts new items to the cache and erases some members if it is too large
     * already.
     * 
     * @throws ItemAlreadyPresentException
     */
    public void insert(Signature item) throws ItemAlreadyPresentException {

        if (cache.size() >= maximalCapacity) {
            Iterator it = cache.keySet().iterator();
            int size = cache.size() / cachePurgeRatio;
            Debug.print(2, "Purging the cache.....");

            ArrayList keys = new ArrayList();

            try {
                for (int i = 0; i < size; ++i) {
                    for (int j = 0; j < currentPurgeIndex; ++j)
                        it.next();

                    keys.add(it.next());

                    for (int j = 0; j < cachePurgeRatio - currentPurgeIndex - 1; ++j)
                        it.next();
                }
            } catch (NoSuchElementException e) {
            }

            Iterator it2 = keys.iterator();
            size = keys.size();
            for (int i = 0; i < size; ++i) {
                cache.remove(it2.next());
            }

            currentPurgeIndex = (currentPurgeIndex + 1) % cachePurgeRatio;

            Debug.println(size + " keys purged.");
        }
        //Debug.println("Adding item to the cache: " + item);
        if (cache.put(item, item) != null)
            throw new ItemAlreadyPresentException();
    }

    /**
     * @return true if the specified item is present within the database.
     */
    public boolean isPresent(Signature item) {
        /*
         * boolean oldacc = item.isAcceptingReachable();
         * item.setAcceptingReachable(false); if (!cache.containsKey(item)) {
         * item.setAcceptingReachable(true); if (!cache.containsKey(item)) {
         * item.setAcceptingReachable(oldacc); return false; } }
         * 
         * item.setAcceptingReachable(oldacc); return true;
         */
        return cache.containsKey(item);
    }

    /**
     * Removes the item from the database.
     * 
     * @throws ItemNotPresentException
     *             if the specified object isn't present
     */
    public void remove(Signature item) throws ItemNotPresentException {
        /*
         * boolean oldacc = item.isAcceptingReachable();
         * item.setAcceptingReachable(false); if (cache.remove(item) == null) {
         * item.setAcceptingReachable(true); if (cache.remove(item) == null) {
         * item.setAcceptingReachable(oldacc); throw new
         * ItemNotPresentException(); } } item.setAcceptingReachable(oldacc);
         */
        if (cache.remove(item) == null) {
            throw new ItemNotPresentException();
        }
    }

    /**
     * Tests whether the given state was visited or not.
     * 
     * @param signature
     *            signature to be tested
     * @return true if from this state an accepting state is reachable
     */
    public boolean acceptingReach(Signature signature) {
        /*
         * boolean is; signature.setAcceptingReachable(true);
         * 
         * is = cache.containsKey(signature);
         * signature.setAcceptingReachable(false);
         * 
         * return is;
         */
        try {
            return ((((Signature) cache.get(signature)).acceptingCycleId) >>> 63) != 0;
        } catch (NullPointerException e) {
            return false;
        }
    }

    /**
     * Sets the parameter of acceptance to the state.
     * 
     * @param signature
     *            the state to be changed
     */
    public void setAcceptingReach(Signature signature) {
        try {
            this.remove(signature);
        } catch (ItemNotPresentException e) { // the item was purged out of the
            // cache, nothing to fix
            return;
        }

        signature.setAcceptingReachable(true);

        // this shouldn't throw an exception

        if (cache.put(signature, signature) != null)
            throw new RuntimeException("Inconsistent state cache");

    }

    /**
     * Gets the cycle id.
     * 
     * @param signature
     *            the signature for which we want the cycle id
     * @return the cycle id
     */
    public long getCycleId(Signature signature) {
        Signature sig = (Signature) cache.get(signature);
        return (sig.acceptingCycleId & (~((long) 1 << 63)));
    }

    /**
     * Sets the signature to the new cycle id.
     * 
     * @param signature
     *            the signature
     * @param id
     *            the cycleid
     */
    public void setCycleId(Signature signature, long id) {
        Signature sig = (Signature) cache.get(signature);
        if (((sig.acceptingCycleId >> 63) & 1) != 0)
            sig.acceptingCycleId = id | ((long) 1 << 63);
        else
            sig.acceptingCycleId = id & (~((long) 1 << 63));

    }

    /**
     * Updates the signature with new information - useful for fast signature change.
     * @param signature signature to be updated.
     */
    public void updateItem(Signature signature) {
        try {
            this.remove(signature);
        } catch (ItemNotPresentException e) { // the item was purged out of the
            // cache, nothing to fix
            return;
        }

        // this shouldn't throw an exception
        if (cache.put(signature, signature) != null)
            throw new RuntimeException("Inconsistent state cache");

    }

    /**
     * Clears the cache.
     */
    public void clear() {
        cache.clear();
    }

    /**
     * The cache is implemented via HashSet. The items stored in the HashSet are
     * state identifiers.
     */
    private HashMap cache;

    /**
     * The load factor of the hashset. The factor value can be set between 0 and
     * 1. The lower values improves time performance, but extends the memory
     * requirements.
     */
    private final float load = 0.75f;

    /**
     * Determines the maximal count of items stored within the cache
     */
    private final int maximalCapacity;

    /**
     * Vars for purging the cache
     */
    private final int cachePurgeRatio = 8;

    /**
     * Denotes the last purge index.
     */
    private int currentPurgeIndex = 0;
}
